ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpa/minimal-coverage/main.cpp

   1 #include <stdio.h>
   2 #include <iostream>
   3 #include <list>
   4
   5 using namespace std;
   6
   7 #define foreachin(it,s) for (typeof(s.begin()) it = (s).begin(); it != (s).end(); it++)
   8
   9 typedef pair<int, int> Intervalo;
  10 typedef list<Intervalo> LIntervalo;
  11
  12 bool compararPorPrimeraComp(const Intervalo& p1, const Intervalo& p2){
  13         return p1.first < p2.first;
  14 }
  15
  16 bool resolver(LIntervalo& intervalos, int limite, LIntervalo& solucion) {
  17         intervalos.sort(compararPorPrimeraComp);
  18         int final = 0; // mayor coordenada cubierta hasta ahora
  19         int r_i = 0;   // mayor coordenada hasta ahora alcanzada
  20         Intervalo parActual = Intervalo(0, 0); // posible candidato a ser agregado
  21
  22         foreachin (it, intervalos) {
  23                 // si la primera componente esta mayor que final, ya miramos
  24                 // todo el C, entonces hay que agregar el intervalo
  25                 if (it->first > final) {
  26                         solucion.push_back(parActual);
  27                         final = r_i; // muevo el borde final
  28                 }
  29                 // si la primera componente es menor que final miro si el intervalo sirve
  30                 if (it->first <= final) {
  31                         // sirve si llega mas lejos que lo que hay hasta ahora
  32                         if (it->second > r_i) {
  33                                 r_i = it->second;
  34                                 parActual = *it;
  35                                 // si ademas ya llegue al limite, termine
  36                                 if (r_i >= limite) {
  37                                         solucion.push_back(parActual);
  38                                         break;
  39                                 }
  40                         }
  41                 } else {
  42                         // hay un hueco que no puedo cubrir con ningun intervalo
  43                         break;
  44                 }
  45         }
  46
  47         return r_i >= limite;
  48 }
  49
  50 int main(int argc, char **argv)
  51 {
  52         int casos;
  53         cin >> casos;
  54         while (casos > 0) {
  55                 casos--;
  56                 int limite, x, y;
  57                 cin >> limite;
  58                 x = 1;
  59                 y = 1;
  60                 // cargo intervalos
  61                 LIntervalo intervalos;
  62                 while (y != 0 || x != 0) {
  63                         scanf ("%d %d", &x, &y);
  64                         if (x != 0 || y != 0) {
  65                                 if (x < y) { //para no cargar intervalos inutiles
  66                                         intervalos.push_front(Intervalo(x,y));
  67                                 }
  68                         }
  69                 }
  70                 // resuelvo instancia
  71                 LIntervalo solucion;
  72                 if (resolver(intervalos, limite, solucion)) {
  73                         cout << solucion.size() << endl;
  74                         foreachin (it, solucion) {
  75                                 cout << it->first << " " << it->second << endl;
  76                         }
  77                 } else {
  78                         cout << 0 << endl;
  79                 }
  80                 cout << endl;
  81         }
  82 }
  83